#define null 0
#include "stdio.h"
#include "stdlib.h"
#include "math.h"
#pragma warning(disable:4996)
typedef struct
{ float coef;
  int	expn; }term;
typedef  int status;
typedef struct Lnode
{
	term		data;
	struct Lnode	*next;
}*Link, *Linklist;

int cmp( term a, term b ) /* 比较函数，依a的指数值<（或=、或>）b的指数值，分别返回+1、0、和-1//int cmp (term a,term b); */
{
	if ( a.expn == b.expn )
		return(0);
	else return( (a.expn - b.expn) / abs( a.expn - b.expn ) );
}


void Orderinsert( Linklist &L, term e, int (*comp)( term, term ) ) /* 顺序插入 */
{
	Link o, p, q;
	q	= L;
	p	= q->next;
	while ( p && comp( p->data, e ) < 0 )

	{
		q = p; p = p->next;
	}
	o	= (Link) malloc( sizeof(Lnode) );
	o->data = e;
	q->next = o;
	o->next = p;
}


status LocateElem( Linklist L, term e, Link &s, Link &q, int (*comp)( term, term ) ) /* 定位 */
{
	Link p; s = L;
	p = s->next;
	while ( p && comp( p->data, e ) != 0 )
	{
		s = p; p = p->next;
	}
	if ( !p )
	{
		s = q = null; return(0);
	}else                            { q = p; return(1); }
}


void Delnext( Linklist &L, Link s ) /*删除结点 */
{
	Link q = s->next;
	s->next = q->next;
	free( q );
}


void Orderinsertmerge( Linklist &L, term e, int (*compara)( term, term ) ) /* 顺序混合插入 */
{
	Link q, s;
	if ( LocateElem( L, e, s, q, compara ) )
	{
		q->data.coef += e.coef;
		if ( !q->data.coef )
		{
			Delnext( L, s );
		}
	}else Orderinsert( L, e, compara );
}


void Creatpolyn( Linklist &p, int m ) /* 建立链表 */
{
	term	e;
	int	i;
	p = (Link) malloc( sizeof(Lnode) ); p->next = null;

	printf( "\n请输入%d个系数和指数用空格符间隔：\n", m );
	for ( i = 1; i <= m; i++ )
	{
		scanf( "%f%d", &e.coef, &e.expn );
		if ( e.coef == 0 )
		{
			printf( "请重新输入系数和指数" );
			scanf( "%f%d", &e.coef, &e.expn );
		}
		Orderinsertmerge( p, e, cmp );
	}
}


void DestroyList( Linklist &L )   /* 销毁链表 */
{
	Link p;
	while ( L->next )
	{
		p = L->next; L->next = p->next;
		free( p );
	}
	free( L );
}


void add( Linklist La, Linklist Lb, Linklist &Lc ) /* Lc= La*Lb */
{
	Link qb; term b;
	qb = Lb->next;
	while ( qb )
	{
		b = qb->data;
		Orderinsertmerge( La, b, cmp );
		qb = qb->next;
	}
	DestroyList( Lb );                              /* 销毁链表Lb */
}


void cf( Linklist &La, Linklist &Lb, Linklist &Lc )     /* 乘法函数 */
{
	Link	qa, qb, qc;
	term	e;
	qa	= La->next;
	qc	= Lc;
	while ( qa )
	{
		qb = Lb->next;
		while ( qb )
		{
			e.coef	= qa->data.coef * qb->data.coef;
			e.expn	= qa->data.expn + qb->data.expn;
			if ( e.coef != 0.0 )
				Orderinsertmerge( qc, e, cmp );
			qb = qb->next;
		}
		qa = qa->next;
	}
	DestroyList( La );
	DestroyList( Lb );
}


void printpolyn( Linklist p ) /* 输出方式 */
{
	Link q;
	q = p->next;
	printf( "    系数    指数\n" );
	while ( q )
	{
		printf( "%8.2f  %-d\n", q->data.coef, q->data.expn );
		q = q->next;
	}
}


/* 请在此处写上将一元多项式横向输出的函数 */
void printpolyn2( Linklist p ) /* 输出方式 2 */
{
	Link q;
	q = p->next;
	printf( "p(x)=" );
	if ( q == null )
	{
		printf( "为空\n" );
		return;
	}
	printf( "%8.2f*X^%d", q->data.coef, q->data.expn );
	q = q->next;
	while ( q )
	{
		if ( q->data.coef > 0 )
			printf( "+%8.2f*X^%d", +q->data.coef, q->data.expn );
		else if ( q->data.coef < 0 )
			printf( "-%8.2f*X^%d", -q->data.coef, q->data.expn );
		q = q->next;
	}
	printf( "\n" );
}


int main()
{
	int		x;
	Linklist	L1, L2, L3;
	printf( "\n请输入第一个一元多项式的项数:\n" );
	scanf( "%d", &x );
	Creatpolyn( L1, x );
	printpolyn( L1 );
	printpolyn2( L1 );

	printf( "\n请输入第二个一元多项式的项数:\n" );
	scanf( "%d", &x );
	Creatpolyn( L2, x );
	printpolyn( L2 );
	printpolyn2( L2 );

	Creatpolyn( L3, 0 );
	cf( L1, L2, L3 );
	printf( "\n相乘后的一元多项式是:\n" );
	printpolyn( L3 );
	printpolyn2( L3 );
}